package one.three.fortySeven;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<Item> {

	private Node<Item> first;
	private int n;

	public Stack() {
		first = null;
		n = 0;
	}

	public boolean isEmpty() {
		return first == null;
	}

	public int size() {
		return n;
	}

	public void push(Item item) {
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
		n++;
	}

	public Item pop() {
		if (isEmpty()) {
			throw new NoSuchElementException("Stack underflow");
		}
		Item item = (Item) first.item;
		first = first.next;
		n--;
		return item;
	}

	public Stack<Item> catenation(Stack<Item> s1, Stack<Item> s2) {
		if (s1 == null) {
			return s2;
		}
		if (s2 == null) {
			return s1;
		}
		if (s1 != null && s2 != null) {
			Item[] a1 = (Item[]) new Object[s1.n];
			Item[] a2 = (Item[]) new Object[s2.n];
			Stack<Item> r = new Stack<Item>();
			int i = 0;
			while (!s1.isEmpty()) {
				a1[i] = s1.pop();
				i++;
			}
			i = 0;
			while (!s2.isEmpty()) {
				a2[i] = s2.pop();
				i++;
			}
			System.out.println("a1:" + Arrays.toString(a1) + ",a2:" + Arrays.toString(a2));

			for (i = a1.length - 1; i >= 0; i--) {
				r.push(a1[i]);
			}
			for (i = a2.length - 1; i >= 0; i--) {
				r.push(a2[i]);
			}
			return r;
		}
		return null;
	}

	private class Node<Item> {
		Item item;
		Node<Item> next;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		Node<Item> c = first;
		while (c != null) {
			s.append("[" + c.item + "]");
			c = c.next;
		}
		return s.toString();
	}

	private class LinkedIterator<Item> implements Iterator<Item> {
		private Node<Item> current;

		public LinkedIterator(Node<Item> first) {
			this.current = first;
		}

		@Override
		public boolean hasNext() {

			return current != null;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

		@Override
		public Item next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			Item item = current.item;
			current = current.next;
			return item;
		}

	}

	public static void main(String[] args) {
		Stack<String> s1 = new Stack<String>();
		s1.push("d");
		s1.push("c");
		// System.out.println(s1);
		Stack<String> s2 = new Stack<String>();
		s2.push("b");
		s2.push("a");

		Stack<String> r = s1.catenation(s1, s2);

		System.out.println(r);

	}

}
